Queries in database systems are posed in high level, declarative (non-procedural) languages that are translated into a procedural execution plan. Many relational database management systems employ query optimizers in order to choose a query plan for a given query. The purpose of query optimization is to explore the manners in which this declarative request can be translated into procedural plans and to select the most efficient plan among those explored. The desired query execution plan can consist of a series of primitive database operators, and is typically selected according to a least estimated execution cost.
Conventional query optimizers perform well for the vast majority of time in large independent software vendor (ISV) application deployments. These applications can contain a large quantity of queries (e.g., upwards of 60,000 queries). In large ISV deployments, there are some queries, typically no more than 50 even in the largest deployments, which perform poorly because they are optimized with non-representative or non-worst-case parameter values. These parameterized queries come from prepare-execute-style execution and/or from stored procedures.
For example, a typical bad scenario is one in which a plan based on unusual parameter value (e.g., “sales for the Iceland subsidiary”) is saved in the database system's query plan cache, and then used for a long period of time even as the query is run with other parameter values that need a different plan to run efficiently (e.g., “sales for the US subsidiary”).